#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix)
	{
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		if((matrix.size() < 1) || (matrix[0].size()<1))
			return 0;

		size_t *lastCounts = new size_t[matrix[0].size()],
			*curCounts = new size_t[matrix[0].size()];

		for(size_t i=0;i<matrix[0].size();i++)
		{
			curCounts[i] = (matrix[0][i]=='1');
		}

		int curMaxArea = calMaxRectangle(curCounts,matrix[0].size());
		std::swap(lastCounts,curCounts);
		size_t n = matrix.size(), m = matrix[0].size();
		for(size_t i=1;i<n;i++)
		{
			for(size_t j=0;j<m;j++)
				curCounts[j] = (matrix[i][j]=='0')?0:(lastCounts[j]+1);
			curMaxArea = max(curMaxArea,calMaxRectangle(curCounts,m));
			swap(curCounts,lastCounts);
		}

		return curMaxArea;
    }

private:
	int calMaxRectangle(size_t* counts,size_t len)
	{
		if(len<=0)
			return 0;
		size_t maxArea = 0;
		vector<size_t> leftNG(len),rightNG(len);
		stack<size_t> pos;

		for(size_t i=0;i<len;i++)
		{
			while(!pos.empty())
			{
				if(counts[pos.top()]>=counts[i])
					pos.pop();
				else
					break;
			}

			if(pos.empty())
				leftNG[i] = i;
			else
				leftNG[i] = i-pos.top()-1;
			pos.push(i);
		}

		while(pos.size()>0)
			pos.pop();

		for(size_t idx=len;idx>0;idx--)
		{
			size_t i = idx-1;
			while(!pos.empty())
			{
				if(counts[pos.top()]>=counts[i])
					pos.pop();
				else
					break;
			}

			if(pos.empty())
				rightNG[i] = len-1-i;
			else
				rightNG[i] = pos.top()-i-1;
			pos.push(i);
		}

		for(size_t i=0;i<len;i++)
		{
			maxArea = max(maxArea,(leftNG[i]+rightNG[i]+1)*counts[i]);
		}
		
		return int(maxArea);
	}
};
#endif
